/*
 * get the sub array with the max sum 
 */

#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
const long int INF = 0 -  10000000;

int maxSum1(const vector<int> & array){
	long int maxSum = INF;
	long int sum =0 ;
	int len = array.size();
	for(int i = 0;i<len;i++){
		sum = 0;
		for(int j = i ;j< len ;j++){
			sum += array.at(j);
			if(sum > maxSum)
				maxSum  = sum;
		}
	}
	cout<<"by method 1 :"<<maxSum<<endl;
	return maxSum;
}
long int max(long int a,long int b){
	return (a > b)? a :b ;
}
int maxSum2(const vector<int> & array){
	int len = array.size();
	long int alli = array.at(len -1);
	long int starti = array.at(len -1);
	for(int i= len -2;i>= 0;i--){
		starti  = max(array.at(i),array.at(i) + starti);
		alli = max(starti,alli);
	}
	cout<<"by method 2 :"<<alli<<endl;
}

int main(){
	ifstream ifs;
	ifs.open("../data/sumOfSubArray.dat");
	vector<int> array;
	int temp;
	while(!ifs.eof()){
		ifs >> temp;
		array.push_back(temp);
	}
	maxSum1(array);
	maxSum2(array);
	return 0;
}
